이 게시물부터 보는 사람은 반드시 스크롤을 내려서 이전 게시물의 “왜 암기를 하죠?” 부분을 잘 읽고 오기 바란다.
다익스트라를 암기해 보자
드디어 정리해도 어렵고 또 어려운 대망의 다익스트라이다. 대기업이나 중견기업 코딩 테스트에서 수험자를 죽이려고 마구마구 찍어내는 지옥 난이도 문제들은 보통 “다익스트라 + 비트마스킹 + DP + 그리디 + 파싱”같은 조합을 쓰고, 일단 다익스트라부터 구현하고 DP나 그리디 구조 파악, 비트마스킹/파싱같은 자잘한 디테일을 잡아가는 방식을 취한다. 물론 내가 풀 수 있는 유형은 아니지만 보통은 그렇다. 그도 그럴 것이 그걸 풀 수 있었으면 인생이 달랐을지도 모르니까 말이다.
어디까지나 나의 방법론은 범부를 위한 코더 가이드에 가깝다. 현학적이고 학구적인 태도에 내 방식은 정면으로 배치되는 것을 알아 뒀으면 좋겠다.
암기 포인트
- 애써서 힙을 구현하려 하지 말자
- 만약 당신이 고지능의 수재라면 직접 구현해서 성능을 뽑아도 된다
- 현재 노드를 거쳐서 다음 노드로 가는게 기존 방법보다 빠르면
- 그 방식의 가중치로 업데이트한다.
- 이것을
min을 쓴다고 생각해서 단순하게 외우자
- v, w같은 추상적인 축약은 쓰면 안 된다
- 반드시 vertex, weight로 다 써서 헷갈림을 방지하자
지능이 높은 사람들의 특징이 추상화에 강한 것이다. 그러한 사람들은 u, v, w가 편하겠지만 우리에게는 아니다. 이것은 평범하거나 그보다 못한 재능에서 출발한 내가 지키는 3원칙이다.
- 변수명은 반드시 구체적이어야 한다
- 코드에서 주석을 떼도 어느 정도 이해되어야 한다
- 주석은 코드의 흐름을 따라야 한다
이러한 3원칙을 어느 정도 지키며 작성된 다익스트라 알고리즘의 코드를 주석을 잘 보면서 따라오길 바란다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
typedef long long ll;
typedef struct {
int vertex;
ll weight;
} Edge;
typedef std::pair<ll,int> pll;
typedef std::priority_queue<pll, std::vector<pll>, std::greater<pll>> pq_ll; // DO NOT MANUALLY IMPLEMENT HEAP!!
// SINCE IMPORTING EXTERNAL LIBRARIES IN C IS NOT ALLOWED, USING C++ INSTEAD, IS MUCH BETTER FOR CODING TEST
#define INF (LLONG_MAX / 4)
void dijkstra_sssp(int n, const std::vector<std::vector<Edge>> &g, int src, std::vector<ll> &dist) {
dist.assign(n, INF);
dist[src] = 0;
pq_ll pq;
pq.push(pll(0, src)); // current distance is zero(before start: status zero), starting point is src
while (!pq.empty()) {
ll current_dist = pq.top().first;
int current_node = pq.top().second;
pq.pop(); // TILL HERE, SAME AS BFS
if (current_dist != dist[current_node]) continue; // something like softer version of assert(current_dist == dist[currunt_size]), so current_dist MUST BE DIST[current_size] to apply for distance recheck/calculation
for (int i = 0; i < (int)g[current_node].size(); i++) {
// BE SURE TO MEMORIZE THIS PART
int next_node = g[current_node][i].vertex;
ll edge_weight = g[current_node][i].weight;
// if getting next_node through current_node, UPDATE distance to current_dist + edge_weight;
int current_update = (int)((current_dist + edge_weight) < dist[next_node]);
dist[next_node] = std::min(current_dist + edge_weight, dist[next_node]) ;
if (current_update) pq.push(pll(dist[next_node], next_node)); // ONLY IF IT IS AN UPDATE TARGET
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<Edge>> g(n);
for (int i = 0; i < m; i++) {
int a, b;
ll c;
std::cin >> a >> b >> c; // 0-indexed: a -> b with weight c
g[a].push_back((Edge){b, c}); // if directed, it's fine with this single line; but
// if undirected, also add below
// g[b].push_back((Edge){a, c});
}
int src;
std::cin >> src;
std::vector<ll> dist;
dijkstra_sssp(n, g, src, dist);
for (int i = 0; i < n; i++) {
if (dist[i] >= INF / 2) std::cout << "-1\n"; // no ways to arrive dist[i]
else std::cout << dist[i] << "\n";
}
return 0;
}
주석 친 포인트가 중요하다. 확실히 보고 기억해야 한다.
소감
이걸 외울 수 있을지 모르겠다. 빌 게이츠가 코드 검수할 때 종이에 출력해서 했다던데, 프린트해서 봐야 하나? 책 10쪽을 외우는 것보다 이것 하나를 외우는 것이 더 고통스러울지도 모르는 일이다. 열심히 해 보는 수밖에는 없지 않을까.